In the RAID (Redundant Array of Independent Disks) architecture for use with a computer system, information is stored distributively among multiple nodes, such as an array of disks or a cluster of networked computers, in a redundant manner that is resilient to individual node failures. See, for example, D. A. Patterson et al., ACM SIGMOD, 17(3):109-116 (1988); P. M. Chen, et al., ACM Computing Surveys, 26(2):145-185 (1994). The RAID architecture improves the reliability, availability, and performance of the computer system and has seen extensive applications in a variety of use cases over the decades since its introduction in the 1980's. See, for example, P. M. Chen, et al., ACM Computing Surveys, 26(2):145-185 (1994); C. Huang et al., USENIX Annual Technical Conference (ATC) (2012); and A. Fikes, Google Faculty Summit (2010).
As distributed storage systems are increasingly being used to store critical as well as sensitive data, the challenge of protecting data confidentiality is imminent. This is discussed, for example, in Gemalto, Tech. Rep. (2014). Nevertheless, the application of existing schemes to practical distributed storage systems can be limited by their complexities (see, e.g., J. Kurihara, S. Kiyomoto, K. Fukushima, and T. Tanaka, “A New (k,n)-threshold Secret Sharing Scheme and its Extension,” ISC, 2008). For example, current schemes typically have much higher encoding and decoding complexities than the erasure codes employed in practice, that offer protection against failure but not against eavesdropping. The reasons are generally twofold: Firstly, erasure codes for distributed storage are typically encoded systematically so that the information symbols appear “in the clear”, without encryption, in the codeword. This trivializes decoding when no erasure occurs and significantly simplifies encoding. In comparison, an eavesdropping-resistant secure scheme does not allow information symbols to appear in the clear and thus the encoding/decoding complexity is increased. Secondly, while there have been extensive studies on optimizing the encoding/decoding complexity of erasure codes and numerous good constructions are known, very little is known about how to design secure schemes with similar optimality. See, for example, M. Blaum, J. Brady, J. Bruck, and J. Menon, “EVENODD: an Efficient Scheme for Tolerating Double Disk Failures in RAID architectures,” IEEE Transactions on Computers, Vol. 44, No. 2, pp. 192-202, 1995; and L. Xu, V. Bohossian, J. Bruck, and D. G. Wagner, “Low-density MDS codes and factors of complete graphs,” IEEE Transactions on Information Theory, Vol. 45, No. 6, pp. 1817-1826, 1999.
Computer data storage techniques could advantageously utilize low-complexity schemes to store information in a distributed manner that is resilient to node failures and resistant to node eavesdropping. This document addresses these issues.